package com.lun.medium;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class BinarySearchTreeIterator {

	//方法一：我写的
	public static class BSTIterator {

		private LinkedList<Object[]> stack;
		
	    public BSTIterator(TreeNode root) {
	    	stack = new LinkedList<>();
	    	stack.push(new Object[] {root, 0});
	    }
	    
	    public int next() {
	    	while(!stack.isEmpty()) {
	    		Object[] arr = stack.peek();
	    		TreeNode node = (TreeNode)arr[0];
	    		int state = (int)arr[1];
	    		
	    		if(state == 0) {
	    			if(node.left != null)
	    				stack.push(new Object[] {node.left, 0});
	    			arr[1] = 1;
	    		}else{
	    			stack.pop();
	    			if(node.right != null) 
	    				stack.push(new Object[] {node.right, 0});
	    			return node.val;
	    		}
	    	}
	    	return -1;
	    }
	    
	    public boolean hasNext() {
	    	return !stack.isEmpty();
	    }
	}
	
	//方法二：别人写的
	public static class BSTIterator2 {

		private LinkedList<TreeNode> stack;
		private TreeNode pointer;
		
	    public BSTIterator2(TreeNode root) {
	    	stack = new LinkedList<>();
	    	pointer = root;
	    }
	    
	    public int next() {
	    	while(hasNext()) {
	    		if(pointer != null) {
	    			stack.push(pointer);
	    			pointer = pointer.left;
	    		}else{
	    			TreeNode node = stack.pop();
	    			pointer = node.right;
	    			return node.val;
	    		}
	    	}
	    	return -1;//或抛异常
	    }
	    
	    public boolean hasNext() {
	    	return !stack.isEmpty() || pointer != null;
	    }
	}
	
	//方法三：别人写的2
	public static class BSTIterator3 {

	    private LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
	    
	    public BSTIterator3(TreeNode root) {
	        pushAll(root);
	    }

	    /** @return whether we have a next smallest number */
	    public boolean hasNext() {
	        return !stack.isEmpty();
	    }

	    /** @return the next smallest number */
	    public int next() {
	        TreeNode tmpNode = stack.pop();
	        pushAll(tmpNode.right);
	        return tmpNode.val;
	    }
	    
	    private void pushAll(TreeNode node) {
	        for (; node != null; stack.push(node), node = node.left);
	    }
	}
	
	
}
